﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Shapes;
using System.Xml.Linq;
namespace 寻路径算法
{

    public enum NodeType
    {
        Start,
        End,
        Executive,
        Process
    }

    // --- Port.cs ---
    // 简化后的 Port 类，仅包含名称和所属节点
    public class Port
    {
        public string Name { get; }
        public Node Owner { get; }

        public Port(string name, Node owner)
        {
            Name = name ?? throw new ArgumentNullException(nameof(name));
            Owner = owner ?? throw new ArgumentNullException(nameof(owner));
        }
    }

    // --- Node.cs ---
    // Node 类现在使用一个集合作为所有端口
    public class Node
    {
        public string Id { get; set; }
        public NodeType Type { get; set; }
        public double X { get; set; }
        public double Y { get; set; }

        // 使用一个集合作为所有端口
        public List<Port> Ports { get; } = new List<Port>();

        public Node(string id, NodeType type, double x, double y)
        {
            Id = id;
            Type = type;
            X = x;
            Y = y;

            // 默认添加一个输入和一个输出端口，通过名称区分
            Ports.Add(new Port("Input", this));
            Ports.Add(new Port("Output", this));
        }

        // 方便的方法：根据名称获取端口
        public Port GetPort(string name)
        {
            return Ports.FirstOrDefault(p => p.Name == name);
        }

        // 为了支持从 Port 计算绝对位置
        public Point GetPortAbsolutePosition(Port port)
        {
            const double width = 100.0;
            const double height = 60.0;

            if (port.Name == "Input")
            {
                // 假设输入端口在左侧中间
                return new Point(X - width / 2, Y);
            }
            else if (port.Name == "Output")
            {
                // 假设输出端口在右侧中间
                return new Point(X + width / 2, Y);
            }
            // 默认返回节点中心
            return new Point(X, Y);
        }
    }

    // --- Edge.cs ---
    // Edge 类保持不变，连接两个 Port 对象
    public class Edge
    {
        public Port FromPort { get; }
        public Port ToPort { get; }

        public Edge(Port fromPort, Port toPort)
        {
            FromPort = fromPort ?? throw new ArgumentNullException(nameof(fromPort));
            ToPort = toPort ?? throw new ArgumentNullException(nameof(toPort));
        }

        public Node FromNode => FromPort.Owner;
        public Node ToNode => ToPort.Owner;
    }




    // --- Graph.cs ---
    // Graph 类保持不变，支持节点和边的增删查
    public class Graph
    {
        private readonly Dictionary<Node, HashSet<Node>> _adjacencyList = new Dictionary<Node, HashSet<Node>>();

        public List<Node> Nodes { get; } = new List<Node>();
        public List<Edge> Edges { get; } = new List<Edge>();

        public void AddNode(Node node)
        {
            if (!_adjacencyList.ContainsKey(node))
            {
                Nodes.Add(node);
                _adjacencyList[node] = new HashSet<Node>();
            }
        }

        public void RemoveNode(Node node)
        {
            if (node == null || !_adjacencyList.ContainsKey(node))
                return;

            var edgesToRemove = Edges.Where(e => e.FromNode == node || e.ToNode == node).ToList();
            foreach (var edge in edgesToRemove)
            {
                RemoveEdge(edge); // 现在 RemoveEdge 会处理双向连接
            }

            foreach (var neighbors in _adjacencyList.Values)
            {
                neighbors.Remove(node);
            }

            _adjacencyList.Remove(node);
            Nodes.Remove(node);
        }

        // 修改后的 AddEdge 方法，支持无向图
        public void AddEdge(Edge edge)
        {
            Edges.Add(edge);
            var fromNode = edge.FromNode;
            var toNode = edge.ToNode;

            if (!_adjacencyList.ContainsKey(fromNode))
                AddNode(fromNode);
            if (!_adjacencyList.ContainsKey(toNode))
                AddNode(toNode);

            // 无向图：在 fromNode 的邻居中添加 toNode
            _adjacencyList[fromNode].Add(toNode);
            // 无向图：在 toNode 的邻居中添加 fromNode
            _adjacencyList[toNode].Add(fromNode);
        }

        // 修改后的 RemoveEdge 方法，支持无向图
        public void RemoveEdge(Edge edge)
        {
            if (Edges.Remove(edge))
            {
                var fromNode = edge.FromNode;
                var toNode = edge.ToNode;

                // 无向图：从 fromNode 的邻居中移除 toNode
                if (_adjacencyList.ContainsKey(fromNode))
                {
                    _adjacencyList[fromNode].Remove(toNode);
                }
                // 无向图：从 toNode 的邻居中移除 fromNode
                if (_adjacencyList.ContainsKey(toNode))
                {
                    _adjacencyList[toNode].Remove(fromNode);
                }
            }
        }

        public List<List<Node>> FindAllPathsDFS(Node start, Node end)
        {
            var allPaths = new List<List<Node>>();
            var currentPath = new List<Node> { start };
            var visited = new HashSet<Node> { start };

            DFSRecursive(start, end, currentPath, visited, allPaths);

            return allPaths;
        }

        private void DFSRecursive(Node current, Node end, List<Node> currentPath, HashSet<Node> visited, List<List<Node>> allPaths)
        {
            if (current.Equals(end))
            {
                allPaths.Add(new List<Node>(currentPath));
                return;
            }

            if (_adjacencyList.TryGetValue(current, out var neighbors))
            {
                foreach (var neighbor in neighbors)
                {
                    if (!visited.Contains(neighbor))
                    {
                        visited.Add(neighbor);
                        currentPath.Add(neighbor);

                        DFSRecursive(neighbor, end, currentPath, visited, allPaths);

                        currentPath.RemoveAt(currentPath.Count - 1);
                        visited.Remove(neighbor);
                    }
                }
            }
        }
    }






















    //public enum NodeType
    //{
    //    Power,      // 电源
    //    Executive,  // 执行机构 (如电机、灯泡)
    //    Process     // 过程节点 (如继电器、开关)
    //}

    //public enum PortType
    //{
    //    Input,  // 输入端口
    //    Output  // 输出端口
    //}

    // Node.cs

    // Port.cs
    //public class Port
    //{
    //    public string Name { get; set; }
    //    public PortType Type { get; set; }
    //    public Node Owner { get; set; }

    //    // ✅ 关键：存储连接的边
    //    public List<Edge> ConnectedEdges { get; set; } = new List<Edge>();

    //    public Port(string name, PortType type, Node owner)
    //    {
    //        Name = name;
    //        Type = type;
    //        Owner = owner;
    //    }
    //}


    //public class Node
    //{
    //    public string Id { get; set; }
    //    public NodeType Type { get; set; }
    //    public double X { get; set; }
    //    public double Y { get; set; }

    //    public List<Port> InputPorts { get; set; } = new List<Port>();
    //    public List<Port> OutputPorts { get; set; } = new List<Port>();

    //    // ✅ 用于快速遍历
    //    public List<Edge> OutgoingEdges { get; set; } = new List<Edge>();
    //    public List<Edge> IncomingEdges { get; set; } = new List<Edge>();

    //    public Node(string id, NodeType type, double x, double y)
    //    {
    //        Id = id;
    //        Type = type;
    //        X = x;
    //        Y = y;

    //        InputPorts.Add(new Port("In", PortType.Input, this));
    //        OutputPorts.Add(new Port("Out", PortType.Output, this));
    //    }

    //    public Port GetPort(PortType type, int index = 0)
    //    {
    //        var list = type == PortType.Input ? InputPorts : OutputPorts;
    //        return index < list.Count ? list[index] : null;
    //    }

    //    // 计算端口绝对位置（用于绘图）
    //    public (double X, double Y) GetPortAbsolutePosition(Port port)
    //    {
    //        double centerX = X;
    //        double centerY = Y;

    //        if (port.Type == PortType.Input)
    //        {
    //            return (centerX - 50, centerY); // 左侧
    //        }
    //        else
    //        {
    //            return (centerX + 50, centerY); // 右侧
    //        }
    //    }
    //}

    //// --- Edge.cs ---
    //// Edge 类保持不变，连接两个 Port 对象
    //public class Edge
    //{
    //    public Port FromPort { get; set; }
    //    public Port ToPort { get; set; }

    //    public Edge(Port fromPort, Port toPort)
    //    {
    //        FromPort = fromPort;
    //        ToPort = toPort;
    //    }
    //}
    //public class ClosedLoopResult
    //{
    //    public List<string> Path { get; set; } = new List<string>();
    //    public bool IsValid { get; set; }
    //    public string ErrorMessage { get; set; }
    //}

    //public class CircuitAnalyzer
    //{
    //    private readonly Graph _graph;

    //    public CircuitAnalyzer(Graph graph)
    //    {
    //        _graph = graph;
    //    }

    //    public List<ClosedLoopResult> FindAllClosedLoops()
    //    {
    //        var results = new List<ClosedLoopResult>();
    //        var allLoops = new HashSet<string>(); // 用于去重

    //        // 从每个节点的每个输出端口开始搜索
    //        foreach (var node in _graph.Nodes)
    //        {
    //            foreach (var outputPort in node.OutputPorts)
    //            {
    //                // 每次搜索使用独立的 visited 集合
    //                var visitedNodes = new HashSet<Node>();
    //                var currentPath = new List<Node>();

    //                // 开始 DFS
    //                DFS(node, outputPort, node, visitedNodes, currentPath, results, allLoops);
    //            }
    //        }

    //        return results;
    //    }

    //    private void DFS(Node startNode, Port currentPort, Node currentNode,
    //                    HashSet<Node> visitedNodes, List<Node> currentPath,
    //                    List<ClosedLoopResult> results, HashSet<string> allLoops)
    //    {
    //        // 如果回到起点且路径长度 > 1，找到闭环
    //        if (currentNode == startNode && currentPath.Count > 0)
    //        {
    //            // 构建路径字符串用于去重
    //            var pathIds = currentPath.Select(n => n.Id).ToList();
    //            var loopKey = string.Join("→", pathIds);

    //            if (!allLoops.Contains(loopKey))
    //            {
    //                allLoops.Add(loopKey);

    //                var isValid = ValidateClosedLoop(pathIds);
    //                results.Add(new ClosedLoopResult
    //                {
    //                    Path = pathIds,
    //                    IsValid = isValid,
    //                    ErrorMessage = isValid ? null : "路径中缺少执行机构（Executive）"
    //                });
    //            }
    //            return; // 找到闭环后返回，不继续深入（避免无限循环）
    //        }

    //        // 如果当前节点已访问过（非起点），则跳过
    //        if (visitedNodes.Contains(currentNode) && currentNode != startNode)
    //        {
    //            return;
    //        }

    //        // 标记当前节点为已访问
    //        visitedNodes.Add(currentNode);
    //        currentPath.Add(currentNode);

    //        // 从当前端口出发，遍历所有连接的边
    //        foreach (var edge in currentPort.ConnectedEdges)
    //        {
    //            var nextNode = edge.ToPort.Owner;
    //            var nextPort = edge.ToPort;

    //            // 递归搜索下一个节点的所有输出端口
    //            foreach (var nextOutputPort in nextNode.OutputPorts)
    //            {
    //                DFS(startNode, nextOutputPort, nextNode,
    //                    new HashSet<Node>(visitedNodes), // 传递副本，避免影响其他分支
    //                    new List<Node>(currentPath),    // 传递副本
    //                    results, allLoops);
    //            }
    //        }

    //        // 回溯：移除当前节点（实际上由于传递副本，这里可省略）
    //        // visitedNodes.Remove(currentNode);
    //        // currentPath.RemoveAt(currentPath.Count - 1);
    //    }

    //    private bool ValidateClosedLoop(List<string> path)
    //    {
    //        return path.Any(nodeId =>
    //        {
    //            var node = _graph.Nodes.FirstOrDefault(n => n.Id == nodeId);
    //            return node != null && node.Type == NodeType.Executive;
    //        });
    //    }
    //}
    //// --- Graph.cs ---
    //// Graph 类保持不变，支持节点和边的增删查
    //public class Graph
    //{
    //    private readonly Dictionary<Node, HashSet<Node>> _adjacencyList = new Dictionary<Node, HashSet<Node>>();

    //    public List<Node> Nodes { get; } = new List<Node>();
    //    public List<Edge> Edges { get; } = new List<Edge>();

    //    public void AddNode(Node node)
    //    {
    //        if (!_adjacencyList.ContainsKey(node))
    //        {
    //            Nodes.Add(node);
    //            _adjacencyList[node] = new HashSet<Node>();
    //        }
    //    }

    //    public void RemoveNode(Node node)
    //    {
    //        if (node == null || !_adjacencyList.ContainsKey(node))
    //            return;

    //        var edgesToRemove = Edges.Where(e => e.FromPort.Owner == node || e.ToPort.Owner == node).ToList();
    //        foreach (var edge in edgesToRemove)
    //        {
    //            RemoveEdge(edge);
    //        }

    //        foreach (var neighbors in _adjacencyList.Values)
    //        {
    //            neighbors.Remove(node);
    //        }

    //        _adjacencyList.Remove(node);
    //        Nodes.Remove(node);
    //    }

    //    public void AddEdge(Edge edge)
    //    {
    //        if (edge == null) throw new ArgumentNullException(nameof(edge));

    //        Edges.Add(edge);

    //        // ✅ 关键：在端口上注册这条边，用于遍历
    //        edge.FromPort?.ConnectedEdges.Add(edge);
    //        edge.ToPort?.ConnectedEdges.Add(edge);

    //        // ✅ 可选：在节点上也注册，方便调试和查找
    //        edge.FromPort?.Owner?.OutgoingEdges.Add(edge);
    //        edge.ToPort?.Owner?.IncomingEdges.Add(edge);
    //    }

    //    public void RemoveEdge(Edge edge)
    //    {
    //        if (Edges.Remove(edge))
    //        {
    //            var fromNode = edge.FromPort.Owner;
    //            var toNode = edge.ToPort.Owner;

    //            if (_adjacencyList.ContainsKey(fromNode))
    //            {
    //                _adjacencyList[fromNode].Remove(toNode);
    //            }
    //            if (_adjacencyList.ContainsKey(toNode))
    //            {
    //                _adjacencyList[toNode].Remove(fromNode);
    //            }
    //        }
    //    }

    //    public List<List<Node>> FindAllPathsDFS(Node start, Node end)
    //    {
    //        var allPaths = new List<List<Node>>();
    //        var currentPath = new List<Node> { start };
    //        var visited = new HashSet<Node> { start };

    //        DFSRecursive(start, end, currentPath, visited, allPaths);

    //        return allPaths;
    //    }

    //    private void DFSRecursive(Node current, Node end, List<Node> currentPath, HashSet<Node> visited, List<List<Node>> allPaths)
    //    {
    //        if (current.Equals(end))
    //        {
    //            allPaths.Add(new List<Node>(currentPath));
    //            return;
    //        }

    //        if (_adjacencyList.TryGetValue(current, out var neighbors))
    //        {
    //            foreach (var neighbor in neighbors)
    //            {
    //                if (!visited.Contains(neighbor))
    //                {
    //                    visited.Add(neighbor);
    //                    currentPath.Add(neighbor);

    //                    DFSRecursive(neighbor, end, currentPath, visited, allPaths);

    //                    currentPath.RemoveAt(currentPath.Count - 1);
    //                    visited.Remove(neighbor);
    //                }
    //            }
    //        }
    //    }

    //    /// <summary>
    //    /// 查找所有从电源出发，经过执行机构，并最终回到同一电源的闭环路径。
    //    /// </summary>
    //    public Dictionary<Node, List<List<Node>>> FindClosedLoops()
    //    {
    //        var closedLoops = new Dictionary<Node, List<List<Node>>>();

    //        var powerNodes = Nodes.Where(n => n.Type == NodeType.Power).ToList();

    //        foreach (var powerNode in powerNodes)
    //        {
    //            var allPathsBackToPower = FindAllPathsDFS(powerNode, powerNode);

    //            var validLoops = allPathsBackToPower
    //                .Where(path =>
    //                {
    //                    if (path.Count < 2) return false;
    //                    return path.Skip(1).Take(path.Count - 2).Any(node => node.Type == NodeType.Executive);
    //                })
    //                .ToList();

    //            if (validLoops.Any())
    //            {
    //                closedLoops[powerNode] = validLoops;
    //            }
    //        }

    //        return closedLoops;
    //    }
    //}
}


    //    public enum PortType
    //    {
    //        Input,
    //        Output
    //    }

    //    public class Port
    //    {
    //        public string Name { get; set; }
    //        public int Id { get; set; }
    //        public PortType Type { get; set; }

    //        public Port(string name, PortType type, int id = -1)
    //        {
    //            Name = name;
    //            Type = type;
    //            Id = id;
    //        }

    //        public override string ToString() => $"{Name} ({Type})";
    //    }

 
    //    public enum NodeType
    //    {
    //        Start,
    //        End,
    //        Process
    //}
   

    //    public class Node
    //    {
    //        public string Id { get; set; }
    //        public NodeType Type { get; set; }
    //        public List<Port> InputPorts { get; set; } = new List<Port>();
    //        public List<Port> OutputPorts { get; set; } = new List<Port>();
    //        public double X { get; set; }
    //        public double Y { get; set; }
    //        public List<Edge> ConnectedEdges { get; set; } = new List<Edge>();

    //        public Node(string id, NodeType type, List<Port> inputPorts, List<Port> outputPorts, double x = 0, double y = 0)
    //        {
    //            Id = id;
    //            Type = type;
    //            InputPorts = inputPorts ?? new List<Port>();
    //            OutputPorts = outputPorts ?? new List<Port>();
    //            X = x;
    //            Y = y;
    //        }

    //        // 获取下游邻居（从输出端口出发）
    //        public List<Node> GetNeighbors()
    //        {
    //            var neighbors = new HashSet<Node>();
    //            foreach (var edge in ConnectedEdges)
    //            {
    //                if (edge.FromNode == this)
    //                {
    //                    neighbors.Add(edge.ToNode);
    //                }
    //            }
    //            return neighbors.ToList();
    //        }

    //        // 获取上游节点（连接到输入端口）
    //        public List<Node> GetPredecessors()
    //        {
    //            var predecessors = new HashSet<Node>();
    //            foreach (var edge in ConnectedEdges)
    //            {
    //                if (edge.ToNode == this)
    //                {
    //                    predecessors.Add(edge.FromNode);
    //                }
    //            }
    //            return predecessors.ToList();
    //        }
    //    }

    //public class Edge
    //{
    //    public Node FromNode { get; set; }
    //    public Port FromPort { get; set; }
    //    public Node ToNode { get; set; }
    //    public Port ToPort { get; set; }
    //    public double Weight { get; set; } = 1.0;

    //    public Edge(Node fromNode, Port fromPort, Node toNode, Port toPort, double weight = 1.0)
    //    {
    //        if (fromPort.Type != PortType.Output)
    //            throw new ArgumentException($"FromPort '{fromPort.Name}' of node '{fromNode.Id}' must be an Output port.");
    //        if (toPort.Type != PortType.Input)
    //            throw new ArgumentException($"ToPort '{toPort.Name}' of node '{toNode.Id}' must be an Input port.");

    //        FromNode = fromNode;
    //        FromPort = fromPort;
    //        ToNode = toNode;
    //        ToPort = toPort;
    //        Weight = weight;

    //        FromNode.ConnectedEdges.Add(this);
    //        ToNode.ConnectedEdges.Add(this);
    //    }
    //}

    //public class Graph
    //{
    //    public List<Node> Nodes { get; set; } = new List<Node>();
    //    public List<Edge> Edges { get; set; } = new List<Edge>();

    //    public void AddNode(Node node)
    //    {
    //        if (!Nodes.Any(n => n.Id == node.Id))
    //            Nodes.Add(node);
    //        else
    //            throw new System.ArgumentException($"Node with ID '{node.Id}' already exists.");
    //    }

    //    public void AddEdge(Edge edge)
    //    {
    //        Edges.Add(edge);
    //    }

    //    public List<Node> FindPathBFS(Node startNode, Node endNode)
    //    {
    //        if (startNode == null || endNode == null) return null;
    //        if (startNode == endNode) return new List<Node> { startNode };

    //        var queue = new Queue<Node>();
    //        var visited = new HashSet<Node>();
    //        var parentMap = new Dictionary<Node, Node>();

    //        queue.Enqueue(startNode);
    //        visited.Add(startNode);

    //        while (queue.Count > 0)
    //        {
    //            var currentNode = queue.Dequeue();

    //            foreach (var neighbor in currentNode.GetNeighbors())
    //            {
    //                if (neighbor == endNode)
    //                {
    //                    var path = new List<Node> { endNode };
    //                    var current = currentNode;
    //                    while (current != null)
    //                    {
    //                        path.Add(current);
    //                        current = parentMap.ContainsKey(current) ? parentMap[current] : null;
    //                    }
    //                    path.Reverse();
    //                    return path;
    //                }

    //                if (!visited.Contains(neighbor))
    //                {
    //                    visited.Add(neighbor);
    //                    parentMap[neighbor] = currentNode;
    //                    queue.Enqueue(neighbor);
    //                }
    //            }
    //        }

    //        return null;
    //    }
    //}




    //// 你的原始类，我们扩展支持权重
    //public class Terminal
    //{
    //    public string Name { get; set; }
    //    public string ConnectedTo { get; set; }
    //    public double Weight { get; set; } = 1.0; // 默认权重为1，可自定义
    //}

//// 图的节点（带位置和可视化元素）
//public class Node
//{
//    public string Id { get; set; }
//    public Point Position { get; set; }
//    public Ellipse Visual { get; set; }
//}

//// 图的边（带权重和可视化元素）
//public class Edge
//{
//    public string From { get; set; }
//    public string To { get; set; }
//    public double Weight { get; set; }
//    public Line Visual { get; set; }
//}

//// 图数据结构
//public class Graph
//{
//    public Dictionary<string, Node> Nodes { get; } = new Dictionary<string, Node>();
//    public Dictionary<string, List<string>> AdjacencyList { get; } = new Dictionary<string, List<string>>();
//    public List<Edge> Edges { get; } = new List<Edge>();

//    // 从 Terminal 列表构建图
//    public void BuildFromTerminals(List<Terminal> terminals)
//    {
//        var allNodeNames = new HashSet<string>();
//        foreach (var t in terminals)
//        {
//            allNodeNames.Add(t.Name);
//            allNodeNames.Add(t.ConnectedTo);
//        }

//        // 圆形布局
//        int count = allNodeNames.Count;
//        if (count == 0) return;

//        double centerX = 250, centerY = 250, radius = 150;
//        int index = 0;
//        foreach (var name in allNodeNames)
//        {
//            double angle = 2 * Math.PI * index / (count == 1 ? 2 : count); // 避免除零
//            double x = centerX + radius * Math.Cos(angle);
//            double y = centerY + radius * Math.Sin(angle);
//            Nodes[name] = new Node { Id = name, Position = new Point(x, y) };
//            index++;
//        }

//        // 添加边
//        foreach (var t in terminals)
//        {
//            AddEdge(t.Name, t.ConnectedTo, t.Weight);
//        }
//    }

//    public void AddEdge(string from, string to, double weight)
//    {
//        if (!AdjacencyList.ContainsKey(from))
//        {
//            AdjacencyList[from] = new List<string>();
//        }

//        if (!AdjacencyList.ContainsKey(to))
//        {
//            AdjacencyList[to] = new List<string>();
//        }

//        AdjacencyList[from].Add(to);
//        AdjacencyList[to].Add(from);

//        Edges.Add(new Edge { From = from, To = to, Weight = weight });
//    }

//    public List<string> GetNeighbors(string node) =>
//        AdjacencyList.ContainsKey(node) ? AdjacencyList[node] : new List<string>();
//}

